%----------------------------------------------------------
%    CHAPTER 1
%----------------------------------------------------------
\chapter{形式语言基础}

%----------------------------------------------------------
%    下面是章节开始到2.1之前的内容
%----------------------------------------------------------

计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性，这就是形式语言理论研究的问题。

形式语言诞生于1956年，由chomsky创立。语言研究涉及三个方面：语法、语义和语用；我们侧重语法的研究。

$\divideontimes$形式语言的基本观点是：语言是符号串之集合！（语言就是一句一句话）

$\divideontimes$形式语言理论研究的基本问题是：研究符号串集合的表示方法、结构特性以及运算规律。

%----------------------------------------------------------
%    下面是2.1的内容
%----------------------------------------------------------
\section{形式语言是符号串集合}

\begin{definition}
	\label{def:2.1}
	形式语言：字母表上的符号，按一定的规则组成的所有符号串集合。其中的每个符号串称为句子。
\end{definition}
\begin{definition}
	\label{def:2.2}
	字母表：元素（符号）的非空有限集合；（构成字符串的最基本符号不能再切割了）。
\end{definition}
\begin{definition}
	\label{def:2.3}
	符号串：符号的有限序列。
\end{definition}
在讨论符号串时，注意是基于某个字母表的，例如对于{0，1}构成的字母表，其上的符号串可以是 010，0101110，\ldots\ldots
\begin{definition}
	\label{def:2.4}
	符号串集合：有限个或者无限个符号串组成的集合。
\end{definition}
\begin{definition}
	\label{def:2.5}
	规则：以某种形式表达的在一定范围内共同遵守的规章和制度。这里指符号串的组成规则。
\end{definition}
形式语言概念示例：
\begin{example}[]
	\label{ex:2.1}
	$L_1=\{00,01,10,11\}$;
	
	字母表有$\sum_1 = \{0,1\}$;
	
	句子有：00,01,10,11
\end{example}
\begin{example}[]
	\label{ex:2.2}
	$L_2=\{ab^mc,b^n\mid m>0,n\geqslant 0\}$;
	
	字母表有$\sum_2 = \{a,b,c\}$;
	
	句型1：$ab^mc$,
	
	\qquad 有句子：$abc,abbc,abbbc,\ldots$
	
	句型2：$b^n$,
	
	\qquad 有句子：$\varepsilon,b,bb,bbb,\ldots$
\end{example}
注意：
\begin{enumerate}
	\setlength{\itemindent}{2em}
	\item 句型不代表某一个具体的串，代表一类串；
	\item $m$是大于0的，$n$是大于等于0的；
	\item $b^0=\varepsilon $(空符号串)$,b^1=b,b^2=bb,b^3=bbb,\ldots$；
	\item $L_1$为有限语言，$L_2$为无限语言,包括无限多个符号串。
\end{enumerate}

\subsection{符号串（集合）的运算}
符号串的运算：
\begin{definition}
	\label{def:2.6}
	连接：$\alpha \cdot \beta = \alpha\beta$如$a \cdot b = ab$
\end{definition}
连接：设有$x,y$两个符号串，它们的连接操作是把它们连在一起，结果是$xy$。举个例子，$x=ab$，$y=c$，则连接后的符号串为$xy=abc$。

特例：如果一个字符串和一个空字符串连接的话，其结果为自己本身，即：$x \varepsilon = \varepsilon x = x$

\begin{definition}
	\label{def:2.7}
	或：$\alpha \mid \beta = \alpha$（或者$\beta$）
\end{definition}
\begin{definition}
	\label{def:2.8}
	方幂：$\alpha^n = \displaystyle\prod^n \alpha = \alpha\alpha^{n-1} = \alpha^{n-1}\alpha$
	
	\qquad \qquad \quad $\alpha^0 = \varepsilon$(空符号串)
	
	\qquad \qquad \quad $\alpha^1 = \alpha ; \alpha^2 = \alpha\alpha ;\ldots$
\end{definition}
方幂：设$x$是一个符号串，则$x$的方幂$x^2=xx, x^3=x^2x,\ldots, x^n=x^{n-1}x$。

特例：$x^1=x, x^0=\varepsilon$

\begin{definition}
	\label{def:2.9}
	闭包：$\alpha$的正闭包：$\alpha^+ = \alpha^1 \mid \alpha^2 \mid \ldots \mid \alpha^n  \mid \ldots$
	
	\qquad \qquad \quad $\alpha$的星闭包：$\alpha^* = \alpha^0 \mid \alpha^1 \mid \alpha^2 \mid \ldots \mid \alpha^n  \mid \ldots$
\end{definition}
闭包：设$x$是一个符号串，则$x$的闭包$x^* = x^0 \mid x^1 \mid x^2 \mid x^3 \mid \ldots \mid x^n  \mid \ldots$其中：‘$\mid$’是元符号（描述符号），意义为：或者是，即：$x^*$是一种泛指。

$\divideontimes$ 符号串运算示例

\begin{example}
	\label{ex:2.3}
	\begin{enumerate}
		\setlength{\itemindent}{2em}
		\item $abc \cdot de = abcde$
		\item $ab \mid cd = ab$(或者$cd$)
		\item $(a \mid b)^1 = (a \mid b) = a \mid b$
		
		\qquad $(a \mid b)^2 = (a \mid b)(a \mid b) = aa \mid ab \mid ba \mid bb$
		
		\qquad $(a \mid b)^* = (a \mid b)^0 \mid (a \mid b)^1 \mid (a \mid b)^2 \mid \ldots$
		
		即：$(a \mid b)^* = (a \mid b)^n , n \geqslant 0$
	\end{enumerate}
\end{example}

a或b的星闭包表示由a或b所构成的串（包含空串）,如果不包含空串则写成下面的形式。
$$(a \mid b)^+ = (a \mid b)^n , n>0$$

符号串集合的运算

设$A$和$B$为两个符号串集合，则：
\begin{definition}
	\label{def:2.10}
	乘积：$\rm{AB=\{xy \mid x \in A \text{且} y \in B \}}$
\end{definition}
例如：$U=\{a,b\} V=\{c\} \text{则} UV=\{ac,bc\}$

特例：$\{\varepsilon\}\cdot U=U\cdot \{\varepsilon\}=U \varnothing \cdot U=U\cdot \varnothing =\varnothing$
\begin{definition}
	\label{def:2.11}
	和：$A\cup B = A+B = \{ x \mid x \in A \text{或} x \in B\}$
\end{definition}
找到A或者B中的元素取并集
\begin{definition}
	\label{def:2.12}
	方幂：$A^n = \displaystyle\prod^n A = AA^{n-1} = A^{n-1}A$
	
	\qquad \quad $A^0 = \{\varepsilon\}$
	
	\qquad \quad $A^1 = A;A^2 = AA;A^3=AAA;\ldots$
\end{definition}
方幂是若干个集合进行乘积，所谓方幂就是$x^n  = x^{n-1} x$。

特例：$x^1=x,x^0=\varepsilon$
\begin{definition}
	\label{def:2.13}
	闭包：$A$的正闭包：$A^+ = A^1 \cup A^2 \cup \ldots \cup A^n \cup \ldots$
	
	\qquad \qquad \quad \ $A$的星闭包：$A^* = A^0 \cup A^1 \cup A^2 \cup \ldots \cup A^n \cup \ldots$
\end{definition}
把$A$的一次幂到$n$次幂求并集叫做集合$A$的正闭包，如果考虑$A$的0次幂，包含空串的集合称为$A$的星闭包。

符号串集合运算示例：
\begin{example}[]
	\label{ex:2.4}
	设$A=\{a,b\},B=\{c,d\}$
	
	\quad \ 则$A+B=\{a,b,c,d\}$
	
	\quad \ 则$AB=\{xy\mid x\in A,y\in B\}=\{ac,ad,bc,bd\}$ 
\end{example}
\begin{example}[]
	\label{ex:2.5}
	设$A=\{a\}$
	
	\quad \ 则$A^* = A^0 \cup A^1 \cup A^2 \cup \ldots \cup A^n \cup \ldots$ 
	
	\qquad \quad \ \ $= \{\varepsilon\}+\{a\}+\{aa\}+\{aaa\}+\ldots$
	
	\qquad \quad \ \ $= \{\varepsilon,a,aa,aaa,\ldots\}$
	
	\qquad \quad \ \ $= \{a^n \mid n\geqslant 0\}$
\end{example}
假设A只包含一个符号串a，通过并集运算得到一个包含空串和只由a构成的符号串的集合，它可以看作字母a的一个语言。

我们把A扩展为包含a和b的集合，那A的星闭包是什么呢？
\begin{example}
	\label{ex:2.6}
	设$A = \{A,B\}, A^*=?$
	
	\quad \ \ $\because  A^* = A^0 \cup A^1 \cup A^2 \cup \ldots \cup A^n \cup \ldots$
	
	\qquad \ \ $A^0 = \{\varepsilon\}$
	
	\qquad \ \ $A^1 = A = \{a,b\}$
	
	\qquad \ \ $A^2=A\cdot A = \{a,b\}\cdot \{a,b\}=\{aa,ab,ba,bb\}$
	
	\qquad \ \ $A^3 = A\cdot A^2 = \{a,b\}\cdot \{aa,ab,ba,bb\}=\{aaa,aab,aba,abb,baa,bab,bba,bbb\}$
\end{example}
由上述分析可知，A的星闭包由a和b构成的所有符号串所组成的集合，包括空串。

推论：若A为任一字母表，则A*就是该字母表上的所有符号串（包括空串）的集合。

如果把a和b看成字母表中的两个元素，A的星闭包就是以a和b这两个符号构成的语言，当然这里面是包含空串的。A的星闭包或者A的加闭包实际上是在定义语言，给一个字母表，这个操作就可以把字母表所对应的所有符号串都生成出来。
\subsection{符号串集合的文法描述}
前面已经讨论了语言就是符号串的集合，也介绍了集合的基本操作。但是如果给你一个语言，不管是机器语言还是C++语言，我们如何去描述他呢？这是一个比较深刻的问题。我们需要一种能刻画客观世界规律性的描述方式。从我们计算机现在的手段来讲，一般用一些可数学化描述的方式把客观事物描述出来。比如算法或者数据结构，包括前面讲的形式语言自动机，归根结底还是一种数学化的描述。我们现在说符号串的集合表示一种语言，那么我们如何去描述这种语言呢？其中一种非常重要的工具就叫文法。这个概念很重要！计算机中很多问题都可以用文法来描述，甚至很多你用的事务都可以用文法来描述，比如统计符号串，脚本语言中正则表达式的匹配，实际上都是一种文法的体现。那么什么是文法呢？

\begin{example}
	\label{ex:2.7}
	$L = \{ab^nc\mid n \geqslant 0\}$
	
	\quad \ 字母表：$\sum = \{a,b,c\}$
	
	\quad \ 展开：$L = \{ac,abc,abbc,abbbc,\ldots\}$
\end{example}
假如我们现在有这样一个语言，这个语言包含字符串的形式是$a$、$b$的$n$次幂和$c$的乘积（$n\geqslant 0$），他表示的是字母表上abc这三个字母所构成的一个语言，这个语言所包括的符号串模式是，一个$a$和一个$c$，中间夹了零个或若干个$b$，对于这样一个语言如果我们用文法来描述他的话，应该是什么样子呢？
我们用如下几条文法规则来描述上面语言，文法规则也叫产生式规则，这些规则就构成了上述语言生成的规则。

\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法规则]
	$$S\to aAc$$
	$$A\to bA\mid \varepsilon$$
\end{tcolorbox}

其中$S$和$A$可以理解为一些抽象的变量，如果把$S$看成句子的话，$A$就是句子里的一个短语，后面将$S$和$A$定义为非终结符；$a$、$b$、$c$是字母表中的字母，这里用$\varepsilon$表示空符号串，箭头表示推导或产生的意思，左部产生右部，$\mid$表示或的关系。第二组规则也可以写成两条规则：$A\to bA,A\to \varepsilon$。

怎样利用上述文法规则表示语言L?

从开始符号出发，对符号串中的定义对象（非终结符），采用推导的方法（用其规则右部替换左部）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个句子。

给定下述文法规则，我们分析其所定义的语言：

\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法规则]
	$$S\to aAc$$
	$$A\to bA\mid \varepsilon$$
\end{tcolorbox}


句子产生过程（$\Rightarrow$推导算符）：
\begin{enumerate}
	\setlength{\itemindent}{2em}
	\item $S \Rightarrow a A c \Rightarrow a \varepsilon c=a c $
	\item $S \Rightarrow a A c \Rightarrow a b A c \Rightarrow a b \varepsilon c=a b c $
	\item $S \Rightarrow a A c \Rightarrow a b A c \Rightarrow a b b A c \Rightarrow a b b c$
	
	\qquad \ldots
	
	\ \ $\therefore S \stackrel{+}{\Rightarrow} a b^{n} c, n \geqslant 0$
\end{enumerate}

(1)假定$S$是起始符号，$S$推出$aAc$，再把$A$替换为$\varepsilon$，得到了$a\varepsilon c$，最终得到了$ac$

(2)假定$S$是起始符号，$S$推出$aAc$，把$A$替换为$bA$，再把$A$替换为$\varepsilon$，得到了$ab\varepsilon c$，最终得到了$abc$

(3)假定$S$是起始符号，$S$推出$aAc$，把$A$替换为$bA$，把$A$替换为$bA$，再把$A$替换为$\varepsilon$，得到了$abb\varepsilon c$，最终得到了$abbc$

以此类推，可以得到$ S \stackrel{+}{\Rightarrow} a b^{n} c, n \geqslant 0$，$\Rightarrow$表示只经过一次推导，$+$表示至少经过一次推导，$\stackrel{+}{\Rightarrow}$代表连续推导。

%----------------------------------------------------------
%    下面是2.2的内容
%----------------------------------------------------------

\section{形式语言由文法定义的}
\subsection{什么是文法？}
我们这门课重点讨论上下文无关文法，上下文无关文法可以理解为规则均是由一个非终结符构成的左部推导出右部，这样的文法都可以称之为上下文无关文法。
\begin{definition}
	\label{def:2.14}
	文法（grammar）是规则的有限集，其中的上下文无关文法可以定义为四元组：$\rm{G(Z)=(V_{N}, V_{T}, Z, P)}$
\end{definition}

$\rm{V_{N}}$ : 非终结符集（定义的对象集，如：语法成分等)；后面语法树中的中间节点都是非终结符，从计算的角度看，可以把非终结符看作变量，可以被替换的

$\rm{V_{T}}$ : 终结符集（字母表）

$\rm{Z}$ : 开始符号（研究范畴中，最大的定义对象）；整个推导开始的状态

$\rm{P}$ : 规则集（又称产生式集）；规则集包含若干个产生式，每个产生式左部由单一的非终结符构成，右部是由终结符和非终结符构成的任意符号串，形如:$\rm{A\to \alpha}$或者$\rm{A\to \alpha \mid \beta}$。

其中，描述符号：$\to$（定义为），$\mid$（或者是），文法符号：$\rm{Z,A\in V_N,\alpha ,\beta \in (V_N+V_T)^*}$

$\rm{Z}$和$\rm{A}$都属于非终结符集；$\rm{V_N+V_T}$表示这个集合中的元素要么是终结符要么是非终结符，$\rm{V_N+V_T}$的星闭包代表以这个集合里面元素构成的所有符号串，即把$\rm{V_N+V_T}$集合作为字母表所构成的所有符号串。

\subsection{文法是怎样定义语言的？}

\begin{definition}
	\label{def:2.15}
	设有文法$\rm{G(Z)}$，$\rm{L(G)}$为$G$所定义的语言，则$\rm{L(G)=\left\{x \mid Z \stackrel{+}{=} x, x \in V_{\mathbf{T}}^{*}\right\}}$
\end{definition}

有了文法我们如何定义语言呢？一个语言就是由这个文法所生成的字符串构成的。$G(Z)$是一个文法，$L(G)$为$G(Z)$所定义的语言，他是一个由若干个元素构成的集合，元素是从文法其实符号$Z$经过加推导出的由终结符构成的符号串$x$。这个定义包含两个层面，第一，起始符是文法开始符号$Z$，推导一定是由$Z$开始的；第二，语言中的符号串$x$一定是终结符串，不能含有非终结符，如果含有非终结符还要继续推导，直到这个串中没有非终结符，这样才能形成最终的语言。

即：一个文法所定义的语言，是由该文法开始符号推导出的所有仅含终结符的符号串之集合。其中的每个符号串皆称为句子。

\begin{definition}
	\label{def:2.16}
	标识符:字母开头的字母、数字序列。
\end{definition}
\begin{example}
	\label{ex:2.8}
	标识符的文法。
	
	标识符在我们书写程序的时候会使用，声明一个变量，或者写一个函数就会用到标识符，标识符是不可以以数字开头的。现在标识符的定义也不仅仅包含字母和数字，下划线也可以作为标识符的一部分。
	
	标识符文法的非终结符包括两个部分：$\rm{I}$(标识符)，$\rm{A}$(标识符尾)
	
	终结符包括两个部分：$\ell$(字母)，$d$(数字）
	
	起始符：$\rm{I}$
	
	规则集：$ \rm{I\to \ell A \mid \ell }$
	
	\qquad \qquad $\rm{A\to \ell A \mid dA \mid \varepsilon}$
	
	不难看出，上述文法定义的符号串是一个以字母开头的字母和数字构成的序列。
\end{example}

\begin{example}
	\label{ex:2.9}
	无符号整数文法
	
	能否写出一个无符号整数的文法？可以写成这样的形式$N\to dN\mid d$，其中$d$表示0--9的数字。这个文法很特殊，$N$既出现在了文法的左部又出现在了文法的右部，这就构成了递归的形式，递归是描述无限语言非常有效的方式。无符号整数的元素非常多，用这种方式就可以描述无限个无符号的整数。
\end{example}

上述无符号整数文法规则是否存在问题？请读者自行分析。

$\divideontimes$ 标识符文法所定义的语言求解：

标识符文法是如何表达标识符的呢？如果想看这个文法表示的是什么内容，那要知道这个文法生成的句子(符号串)是什么样子。单独从文法规则是看不出来的，我们需要进行一些简单的运算。

上面构造的标识符文法属于正规文法(定义在后)类，正确性检验较容易；下面给出一个算法：


{
	$$
	\left. 
	\begin{aligned}
		\text{令：}I&=\ell A \mid \ell\\
		A&=\ell A \mid dA \mid \varepsilon
	\end{aligned}
	\right \}
	\Rightarrow
	\text{正规方程式}
	$$
}


$\divideontimes$ 求解$I$值步骤：

这个等式不是代数上的等式，而是符号串的替换：$\rm{I}$可以用$\ell A$或$\ell$替换。
我们要求解$\rm{I}$是什么，从起始符号$\rm{A}$开始，它可以得到$\ell A$或$dA$或$\varepsilon$，那$A$是什么呢？

$A=(\ell \mid d)A,A=(\ell \mid d)^2A,\ldots,A=(\ell \mid d)^nA$。$A=\ell A \mid dA$对应$A=(\ell \mid d)A$，这个等式左边右边都有变量，那右边的变量我们可以用同样的$A$进行替换。我们就可以生成$A=(\ell \mid d)^2A$，同样也可以生成$A=(\ell \mid d)^nA$，只有当$A$推出$\varepsilon$时停止，已经全是终结符串了，最终得到$A=(\ell \mid d)^nA,n\geqslant 0$，当$n=0$时包含了$A$推出$\varepsilon$的情况。再把$A$代入$I=\ell A\mid\ell$中得到了$I = \ell(\ell \mid d)^n,n\geqslant 0$，这是标识符串，起始是字母，后面是由字母和数字构成的符号串。

\begin{example}
	\label{ex:2.10}
	简单算术表达式文法 （这个文法务必记牢）
	
	这个文法的非终结符包含$\rm{E}$(算术表达式)、$\rm{T}$(项)、$\rm{F}$(因式)
	
	终结符包含$i$(变量或常数)$,+,-,*,/,(,)$
	
	起始符是$\rm{E}$，由$\rm{E}$开始推导
	
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=规则]
		规则：$E\to T\mid E+T\mid E-T$
		
		\qquad \quad $T\to F\mid T*F\mid T/F$
		
		\qquad \quad $F\to i\mid (E)$
	\end{tcolorbox}
	
	
\end{example}
此文法定义了算术表达式的层次嵌套结构：

\begin{figure}[H]
	\centering
	\input{chapter2/figures/1.tex}
	\caption{算术表达式的层次嵌套结构}
	\label{fig:2.1}
\end{figure}

定义了优先级，在推导的时候先推$+$、$-$，后推$*$、$/$，从运算的角度，因式先做，实际上对应的是规约的过程，当然这个因式可以包括表达式，可以无限嵌套下去。

算术表达式文法应用示例：

证明  $\rm{i*(i+i-i)}$ 是文法$G(E)$的一个句子 (即合法的算术表达式):

根据 语言定义式\ref{def:2.15}，合法的算术表达式是指：

$\rm{E} \stackrel{+}{\Rightarrow} i *(i+i-i)$成立吗？

首先$i$可能代表的是一个数字、标识符、变量，不管$i$代表的是什么，我们把$i$当成一个终结符来看，我们想证明这个符号串是否是表达式文法定义的句子。

语言由起始符开始经过若干次推导得到的终结符串，这样的串构成的集合称之为语言，反过来说，如果我们要证明这个串是语言中的一个句子，那就看能不能从文法起始符经过加推导得到这个符号串。

$\rm{E\Rightarrow T\Rightarrow T^{*} ~F\Rightarrow T^{*}(E)\Rightarrow T^{*}(E-T)\Rightarrow T^{*}(E+T-T)\Rightarrow i^{*}(E+T-T)\Rightarrow \ldots\Rightarrow i^{*}(i+i-i)}$

经过上述推导，可以看出符号串i*(i+i-i)是表达式文法定义的句子。

$\therefore \rm{E} \stackrel{+}{\Rightarrow} i *(i+i-i)$

%----------------------------------------------------------
%    下面是2.3的内容
%----------------------------------------------------------

\section{主要语法成分的定义}
\subsection{文法的运算问题}
文法有一些基本的运算。文法有两种基本运算：推导，规约。

设$\rm{x, y \in\left(V_{N}+V_{T}\right)^{*},A\to \alpha \in P}$

假设x和y是由终结符和非终结符构成的符号串，$\rm{A\to \alpha}$是一条规则。

\begin{definition}
	\label{def:2.17}
	直接推导($\Rightarrow$)：$\rm{xAy\Rightarrow x\alpha y}$
\end{definition}
这个过程称之为使用上述规则完成的一个推导， 将符号串中的一个非终结符$A$替换成所对应规则的右部$\alpha$，这个过程称之为直接推导。$\Rightarrow$称为直接推导算符。

即：指用产生式的右部符号串替换左部非终结符。

\begin{definition}
	\label{def:2.18}
	加推导($\rm{\stackrel{+}{\Rightarrow}}$)：一个符号串经过上述直接推导若干次得到的一个新的串，简记为$\rm{\alpha \stackrel{+}{\Rightarrow} \beta}$，$\rm{\stackrel{+}{\Rightarrow}}$称为加推导算符。加推导需要至少一次推导。
\end{definition}
即：指一步或一步以上的直接推导运算。
\begin{definition}
	\label{def:2.19}
	星推导($\rm{\stackrel{*}{\Rightarrow}}$)，$\alpha$经过若干次推导得到$\beta$，也可以一步都不推导。$\alpha$可以星推导得到$\alpha$，但是$\alpha$不能加推导得到$\alpha$。
\end{definition}
即：指零步或零步以上的直接推导运算。
\begin{definition}
	\label{def:2.20}
	直接规约($\underset{\pmb{^\cdot}}{\Rightarrow}$)：$\rm{x\alpha  y \underset{\pmb{^\cdot}}{\Rightarrow} xAy}$
	
	推导对应的是自上而下的分析，归约对应自下而上的分析。可以把规约看作是推导的逆运算，$\underset{\pmb{^\cdot}}{\Rightarrow}$称之为直接归约算符。
\end{definition}

即：直接归约是直接推导的逆运算，用产生式的左部非终结符替换右部符号串。

\begin{definition}
	\label{def:2.21}
	加归约($\underset{\pmb{^\cdot}}{\stackrel{+}{\Rightarrow}}$)经过若干次归约，若干次左部替换右部的操作，加归约规定至少归约一次，$\underset{\pmb{^\cdot}}{\stackrel{+}{\Rightarrow}}$为加归约算符。
\end{definition}

即：指一步或一步以上的直接归约运算。

\begin{definition}
	\label{def:2.22}
	星归约($\underset{\pmb{^\cdot}}{\stackrel{*}{\Rightarrow}}$)，若干次的直接归约，可以是零次。
\end{definition}

即：指零步或零步以上的直接归约运算。

\begin{definition}
	\label{def:2.23}
	最左推导($\underset{\ell}{\stackrel{+}{\Rightarrow}}$)——每次推导皆最左非终结符优先。
\end{definition}

\begin{definition}
	\label{def:2.24}
	最左归约($\underset{\pmb{\cdot}\ell}{\stackrel{+}{\Rightarrow}}$)——每次规约皆最左可归约串优先。
\end{definition}

为什么会定义最左推导和最左归约，最左推导和一般的推到相比有什么好处？最左归约和一般的归约相比有什么好处？读者可以思考一下。

\begin{example}
	\label{ex:2.11}
	给定一个符号串$i+i*i$：
	
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=算数表达式文法]
		$$\rm{G(E):E\to T\mid E+T\mid E-T
			T\to F\mid T*F\mid T/F
			F\to i\mid (E)}$$
	\end{tcolorbox}
	
	最左推导（从开始符号出发）过程：
	$$\rm{E\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T\Rightarrow i+T\Rightarrow i+T*F\Rightarrow i+F*F\Rightarrow i+i*F\Rightarrow i+i*i}$$
	$$\rm{\therefore E \underset{\ell}{\stackrel{+}{\Rightarrow}} i+i*i}$$
	最左归约（从符号串出发）过程：
	$$\rm{i+i*i \underset{\pmb{^\cdot}}{\Rightarrow} F+i*i \underset{\pmb{^\cdot}}{\Rightarrow} T+i*i \underset{\pmb{^\cdot}}{\Rightarrow} E+i*i \underset{\pmb{^\cdot}}{\Rightarrow} E+F*i \underset{\pmb{^\cdot}}{\Rightarrow} E+T*i \underset{\pmb{^\cdot}}{\Rightarrow} E+T*F \underset{\pmb{^\cdot}}{\Rightarrow} E+T \underset{\pmb{^\cdot}}{\Rightarrow} E}$$
	$$\rm{\therefore i+i*i \underset{\pmb{\cdot}\ell}{\stackrel{+}{\Rightarrow}} E}$$
\end{example}

既然推导和归约是相逆的过程，那最左推导和最左归约是不是一个互逆的过程？实际上最左推导和最左归约并不互逆。

\subsection{句型、句子和语法树}

设有文法$\rm{G(Z)=(V_N,V_T,Z,P)}$，则：

\begin{definition}
	\label{def:2.25}
	句型：若有$\rm{Z \stackrel{+}{\Rightarrow} \alpha}$，则$\alpha$是句型
\end{definition}

$\alpha$既可以包含终结符也可以包含非终结符。

\begin{definition}
	\label{def:2.25}
	句子：若有$\rm{Z\stackrel{+}{\Rightarrow} \alpha}$，且$\rm{\rm{\alpha \in V_T^*}}$，则$\alpha$是句子。
	即句子是由开始符号加推导出的任一终结符号串。
\end{definition}

句子必须都由终结符构成。

\begin{definition}
	\label{def:2.25}
	语法树：句型（句子）产生过程的一种树结构表示。
\end{definition}

树根——开始符号；树叶——给定的句型（句子）。

树对应了整个推导的过程，反过来说，在上下文无关文法的体系下，一个语法树就对应了一个推导，而且在一些限定条件下，他会唯一对应一个推导。

语法树的构造算法：

\begin{enumerate}
	\setlength{\itemindent}{2em}
	\item 置树根为开始符号；
	\item 若采用了推导产生式：$\rm{A\to x_1x-2\ldots x_n}$，则有子树：
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/2.tex}
		\caption{推导产生式的子树}
		\label{fig:2.2}
	\end{figure}
	\item 重复步骤(2)，直到再没有推导产生式为止
\end{enumerate}

根节点是文法的起始符号，产生式的左部作为子树的树根，产生式的右部作为子树的树叶，重复上述过程，直到没有非终结符可以生成子树了，最终就生成了一个句子。把树的叶子节点称之为这个推导所对应的句型（句子）。

$\divideontimes$如此构造的语法树，其全体树叶（自左至右）恰好是给定的句型（句子）。

$\divideontimes$句型、句子和语法树示例：

\begin{example}
	\label{ex:2.12}
	
	\begin{enumerate}

		\item 证明$\mathrm{(T/F+F)*i}$是一个句型（表达式型）
		\item 画出该句型的语法树。
	\end{enumerate}
	
	
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=算数表达式文法]
		$$
		\rm{E\to T\mid E+T\mid E-T
			T\to F\mid T*F\mid T/F
			F\to i\mid (E)}
		$$
		\begin{enumerate}
			\setlength{\itemindent}{2em}
			\item 证明$(T/F+F)*i$是一个句型（表达式型）
			\item 画出该句型的语法树。
		\end{enumerate}
	\end{tcolorbox}
\end{example}
	
	证明： 
	$\divideontimes$句型$\mathrm{(T/F+F)*i}$的语法树构造：
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/3.tex}
		\caption{语法树构造}
		\label{fig:2.3}
	\end{figure}
	
	$\rm{E\Rightarrow T\Rightarrow T*F\Rightarrow F*F\Rightarrow (E)*F\Rightarrow (E+T)*F\Rightarrow (T+T)*F\Rightarrow (T/F+T)*F\Rightarrow (T/F+F)*F\Rightarrow (T/F+F)*i}$
	
	即：$\rm{E \stackrel{+}{\Rightarrow} (T/F+F)*i}$
	
	\begin{definition}
		\label{def:2.26}
		子树：以任何具有分支的结点为根所形成的树，称为原树的子树。
	\end{definition}
	
	\begin{definition}
		\label{def:2.27}
		简单子树：仅具有单层分支的子树。
	\end{definition}
	
	需要注意的是，\ref{fig:2.3}中红色圈出的部分不是子树，而是树片段，子树的叶子必须是原树的叶子。蓝色和绿色圈出的部分也不是简单子树，黄色圈出的子树才是简单子树。
	
	%----------------------
	%定义label下一个应该是2.28，例子label下一个应该是2.13，图片label下一个应该是2.4
	%----------------------
	\begin{example}
		\label{ex:2.13}
		图2.4为一个\color{red}中文句型\color{black}的语法树：
		\begin{figure}[H]
			\centering
			\input{chapter2/figures/4.tex}
			\caption{中文句型的语法树}
			\label{fig:2.4}
		\end{figure}
		为什么要定义句柄？请读者思考这个问题。
		
	\end{example}
	\subsection{短语、简单短语和句柄}
	$\divideontimes$ 设文法G(Z),x y是一个句型，则：
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/5.tex}
		\caption{G(Z)的语法树}
		\label{fig:2.5}
	\end{figure}
	
	\begin{definition}
		\label{def:2.28}
		短语——若$\mathrm{Z} \stackrel{+}{\Rightarrow} x \mathrm{Ay} \stackrel{+}{\Rightarrow} x \alpha y$，则$\alpha$是句型$x \alpha y$关于A的短语(A是$\alpha$的名字);
	\end{definition}
	$\divideontimes$ 任一子树的\color{red}树叶全体\color{black}(具有共同\color{red}祖先\color{black}的叶节点符号串)皆为\color{red}{短语}\color{black}；
	
	\begin{definition}
		\label{def:2.29}
		简单短语——若$\mathrm{Z} \stackrel{+}{\Rightarrow} x \mathrm{Ay} \stackrel{}{\Rightarrow} x \alpha y$，则$\alpha$是句型$x \alpha y$关于A的短语(A是$\alpha$的名字);
	\end{definition}
	简单短语是通过一步推导出来的
	$\divideontimes$ 任一子树的\color{red}树叶全体\color{black}(具有共同\color{red}父亲\color{black}的叶节点符号串)皆为\color{red}{简单短语}\color{black}；
	\begin{definition}
		\label{def:2.30}
		句柄——一个句型的\color{red}最左简单短语\color{black}称为该句型的\color{red}句柄
	\end{definition}
	\begin{example}
		\label{ex:2.14}
		图2.5为一个算术表达式(型)的语法树:
		
		\begin{figure}[H]
			\centering
			\input{chapter2/figures/6.tex}
			\caption{算术表达式(型)的语法树}
			\label{fig:2.6}
		\end{figure}
		
	\end{example}
	
	\noindent 句型：$\rm {E+F-T/F*i}$\\
	短语：$\rm {E+F-T/F*i,E+F,F,T/F*i,T/F,i}$\\
	简单短语：$\rm {F,T/F,i}$\\
	句柄：$\rm {F}$\\
	$\divideontimes$ 一类典型的综合例题：
	\begin{example}
		\label{ex:2.15}
		$\rm{G(S):S \to aAcBe;A\to Ab|b;B\to d}$\\
		$\divideontimes$ 给定符号串$\alpha$:$\rm{aAbcde}$
		\begin{enumerate}

			\item 证明$\alpha=\rm{aAbcde}$是一个句型;
			\item 画出句型$\alpha$的语法树;
			\item 指出$\alpha$中的短语、简单短语和句柄
		\end{enumerate}
	\end{example}
	\begin{enumerate}
		
		\item 证明$\alpha$是由起始符号可以推导出的一个符号串就可以了
		\begin{enumerate}
			
			\item $S \stackrel{}{\Rightarrow} $aAcBe $\stackrel{}{\Rightarrow}$ aAbcBe $\stackrel{} {\Rightarrow} $aAbcde
			\item 语法树如右图:
			\item 短语、简单短语和句柄:\\
			短语:$\rm{aAbcde,Ab,d}$\\
			简单短语:$\rm{Ab,d}$\\
			句柄:$\rm{Ab}$
		\end{enumerate}
		\item 每使用一条规则就把他所对应的子树片段画出来，一层一层画，就可以把这个树画出来
	\end{enumerate}
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/7.tex}
		\caption{G(S)的语法树}
		\label{fig:2.7}
	\end{figure}
	
	%这里好像怪怪的
	\section{两种特性文法} 
	设有文法:$\rm{G(Z)=\left(V_{N}, V_{T}, Z, P\right)}$
	\subsection{递归文法}
	\begin{definition}
		\label{def:2.31}
		设$\rm{A \in V_{N}, x, y \in\left(V_{N}+V_{T}\right)^{*}}$,则;若$\rm{A \stackrel{+}{\Rightarrow} xAy}$,:称文法具有\color{red}递归性\color{black};
	\end{definition}
	A是一个非终结符，若A经过若干次推导可以得到xAy，x和y是由终结符和非终结符构成的集合上的符号串，则称A所在的文法具有递归性。A经过若干次推导，推导得到的中间结果里面仍然含有A，就是A又生成了A。如果在上下文无关文法中，A可以无限的推导，这样我们得到了无限生成字符串的手段。\\
	\color{red}特别\color{black}:若$A \rightarrow A\alpha$,称文法具有\color{red}直接左递归性\color{black};\\
	$A \rightarrow \alpha A$,称文法具有\color{red}直接右递归性\color{black}。\\
	如果文法中存在这样的产生式，其左部和右部都含有非终结符A，并且A在产生式右部的最左端，称这样的文法叫直接左递归文法。同理，如果产生式在左部和右部同时含有非终结符A，并且A在产生式右部的最右端，称这样的文法叫直接右递归文法。\\
	如：
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=直接左递归文法]
		$\rm{G1(S):S\to Sb|a}$
	\end{tcolorbox}
	
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=直接右递归文法]
		$\rm{G2(S):S\to bS|a}$
	\end{tcolorbox}
	
	$\rm{G1(S)}$和$\rm{G2(S)}$是正则文法\\
	$\divideontimes$递归文法是定义无限语言的工具（递归文法定义的语言有无限个句子）！！
	\subsection{二义性文法}
	\begin{definition}
		\label{def:2.32}
		若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。
	\end{definition}
	一个文法中含有一个句型，这个句型具有两棵及以上不同的语法树，即可以用不同的语法树来生成同一个句型，我们就称这个文法是二义性文法。
	\begin{example}
		\label{ex:2.16}
		算术表达式的另一种文法:
		
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=算术表达式的另一种文法]
			$\rm{G^{\prime}(E): E \rightarrow E+E|E-E| E * E|E / E| \text { (E) } \mid i;}$i(变量或常数)
		\end{tcolorbox}
		
	\end{example}
	这个算不算是一个算术表达式的文法？\\
	$\because$句型  $\mathrm{i}+\mathrm{i} * \mathrm{i}$ 有两棵 不同的语法树 (右图):\\
	左边的语法树先计算乘号，右边的语法树先计算加号。上述文法有没有考虑加减乘除的优先级？该文法没有考虑，这导致对于同一个表达式会有不同的分析。\\
	如果用【例2.10】给出的算术表达式文法，就不存在二义性。\\
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/8.tex}
		\caption{不同的语法树}
		\label{fig:2.8}
	\end{figure}
	
	$\therefore$ $\rm{G^{\prime}(\mathbf{E})}$是二义性文法。二义性文法会引起歧义，应尽量避免之！
	\section{文法的等价变换}
	\subsection{文法的等价性}
	变换的依据是文法的等价性
	\begin{definition}
		\label{def:2.33}
		设G1、G2是两个文法，若L(G1)=L(G2)，则称G1与G2等价，记作G1≡G2。
	\end{definition}
	如果文法G1和G2生成的语言是完全相同的，那么G1和G2这两个文法就是等价的。\\
	即：文法的等价性是指他们所定义的语言是一样的
	\begin{example}
		\label{ex:2.17}
		G1和G2分别对应两个文法，G1是一个直接右递归文法，G2是一个直接左递归文法\\
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法规则]
			$\rm{G1:S->aS|a}$;\\
			$\rm{G2:S->Sa|a}$
		\end{tcolorbox}
		
	\end{example}
	
	\noindent $\rm{L\left(G_{1}\right)=\{a, \text { aa, aaa, } \ldots\}=\left\{a^{n} \mid n \geqslant 1\right\}}$\\
	$\rm{L\left(G_{2}\right)=\{a, a a, \quad a a a, \ldots\}=\left\{a^{n} \mid n \geqslant 1\right\}}$\\
	$\rm{\therefore \mathrm{L}\left(G_{1}\right)=\mathrm{L}\left(G_{2}\right)}$
	即  $\rm{G_{1} \equiv G_{2} }$\\
	【注】一个语言，其描述文法并不唯一。\\
	一个语言可以对应无数组文法描述，从这个角度说，如果一个文法描述了一个语言，那么我们是否有其他文法可以描述同样的语言呢？我们可以找到另外一个文法，这个文法没有歧义。
	\subsection{文法变换方法}
	在实际工作中，人们总是希望定义一种语言的文法尽可能地简单；另外，某些常用的语法分析技术也会对文法提出一定的要求或限制。为了适应上述要求，有时需要对文法进行必要的改写—通常称为文法变换，当然改写后的文法要与原文法等价。（文法变化具有技巧性）\\
	这里重点介绍三类变换：
	\begin{enumerate}
		
		\item 删除无用的产生式（文法的化简）；
		\item 删除ε产生式；（文法的右部是一个空串，我们要把他删除掉）
		\item 常用的三种文法变换方法：（是我们一些常见的文法变换方法，这种方法比我们前面公式化要简单很多）\\
		\textcircled{1}必选项法；\\
		\textcircled{2}可选项法；\\
		\textcircled{3}重复可选项法。\\
		这三种方法会贯穿我们后面语法分析的部分。
	\end{enumerate}
	\subsection{文法变换方法1}
	\uppercase\expandafter{\romannumeral1}文法的化简\\
	文法化简是指消除如下无用产生式：
	\begin{enumerate}
		\item 删除 A->A 形式的产生式(自定己)；
		\item 删除不能从其推导出终结符串的产生式(不终结)；
		\item 删除在推导中永不使用的产生式(不可用)。
	\end{enumerate}
	
	刚开始写文法的时候很难写出没有冗余的文法，当存在上述情况时如何处理？对于自定己产生式很容易找到，下面说一下后两种情况的处理方法。\\
	$\divideontimes$ 删除不终结产生式的算法：
	\begin{enumerate}
		
		\item 构造能推导出终结符串的非终结符集$\mathrm{V}_{\mathrm{VT}}:$
		\begin{enumerate}
			\item 若有$A->\alpha$且$\alpha \in V_{T}^{*}$; 则令$A \in V_{V T}$;
			\item 若有$\mathrm{B}->\beta$且$\beta \in\left(\mathrm{V}_{\mathrm{T}}+\mathrm{V}_{\mathrm{VT}}\right)^{*}$ ; 则令$\mathrm{B} \in \mathrm{V}_{\mathrm{VT}}$ ;
			\item 重复步骤\textcircled{1} \textcircled{2},直到$V_{V T}$不再扩大为止。
		\end{enumerate}
		
		\item 删除不在$V_{V T}$中的所有非终结符(连同其产生式)。
	\end{enumerate}
	
	想消除掉不终结的产生式，但是我们不容易求不终结的产生式，那我们可不可以求出哪些产生式是终结的。这个算法定义了$V_{V T}$。
	
	\textcircled{1}对于$A->\alpha$且$\alpha \in V_{\mathrm{T}}^{*}$,A可以推出终结符，则把A放入$V_{V T}$,把产生式右部是终结符串的变量放入$V_{V T}$中
	
	\textcircled{2}B->$\beta$这个产生式的右部是由终结符或$V_{V T}$中元素 构成的符号串，我们就把B看作可终结的，把B放入$V_{V T}$中
	
	\textcircled{3}这个过程反复不断的执行，直到$V_{V T}$不再扩大为止,如果这个符号不在$V_{V T}$中，我们就称C为不终结产生式的左部，我们把C和包含C的所有产生式删除。
	
	$\divideontimes$ 删除不可用产生式的算法：
	\begin{enumerate}
		
		\item 构造可用的非终结符集$V_{U S}$
		\begin{enumerate}
			\item 首先令$Z \in V_{U S}$;(Z为文法\color{blue}开始符号\color{black})
			\item 若有$\mathrm{Z} \stackrel{+}{\Rightarrow}\ldots A \ldots$,则令$ A \in V_{U s}$ ;
			\item 重复步骤\textcircled{2},直到$V_{V T}$不再扩大为止。
		\end{enumerate}
		
		\item 删除不在$V_{V T}$中的所有非终结符(连同其产生式)。
	\end{enumerate}
	
	不可用产生式就是由起始符号不能推导出来的非终结符所对应的产生式，我们称这样的产生式为不可用产生式。
	
	找不可用产生式和不终结的产生式，他们的思路是一模一样的，一个是从终结符开始找，不可用是从起始符号开始找，只是方向有区别，算法是一样的。
	
	首先定义一个集合$V_{V T}$,文法的开始符号都放在$V_{V T}$ 中，如果Z经过若干次推导，将推导出的符号串中的非终结符放入$V_{V T}$中，重复执行这样的过程直到$V_{V T}$不再扩展。最后，删除不在VUS中的所有非终结符连同其产生式。
	
	运用上面三条规则来做一下例2.16。
	\begin{example}
		\label{ex:2.18}
		化简下述文法：\\
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法规则]
			$\rm{G(S):  S\to Be | Ec}$\\
			$\rm{A\to Ae | e | A}$\\
			$\rm{B\to C e | A f}$\\
			$\rm{C\to Cf ; D\to f ; G\to b}$\\
		\end{tcolorbox}
		
	\end{example}
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/9.tex}
		\caption{文法化简示意图}
		\label{fig:2.9}
	\end{figure}
	
	2.哪些非终结符对应的是不可终结的符号串？CE\\
	3.起始符号到达不了的非终结符 DG\\
	\uppercase\expandafter{\romannumeral2}删除 ε产生式\\
	$\divideontimes$ 假定文法G(Z);$\rm{\varepsilon \equiv L(G)}$
	【算法】\\
	1.首先构造可以推出空串的非终结符集:$\mathrm{V}_{\varepsilon}$\\
	\textcircled{1}若有$\rm{A \to ε}$;则令$A \in \mathrm{V_{\varepsilon}}$\\
	\textcircled{2}若有$\rm{B\to A_{1} \ldots A_{n}}$且全部$\rm{A_{i} \in V_{\varepsilon}}$; 则令$\rm{B \in V_{\varepsilon}}$; \\
	\textcircled{3}重复步骤\textcircled{1} \textcircled{2},直到$\rm{V_{\varepsilon}}$不再扩大为止。\\
	2.删除G(Z)中的$\rm{A \to ε}$形成的产生式;\\
	3.依次改写G(Z)中的产生式$\rm{A\to X_{1} X_{2} \ldots X_{n}}$:若有$\rm{X_{\mathrm{i}} \in \mathrm{V}_{\varepsilon}}$,则用$\rm{\left(X_{i} \mid \varepsilon\right)}$替换之(一个分裂为两个);\\
	$\divideontimes$ 若有j个$\rm{X_{i} \in V_{\varepsilon}}$,则一个产生式将分裂为$2^{\mathrm{j}}$个！\\
	$V_{\varepsilon}$中的非终结符，经过若干次推导可以推导出空串\\
	\textcircled{1}首先找直接能推出空串的产生式，把他的左部加入$\rm{V_{\varepsilon}}$\\
	\textcircled{2}假设产生式右部都是能推导出空串的符号，即$\rm{A_{1} \ldots A_{n}}$且全部$\rm{A_{i} \in V_{\varepsilon}}$，那么产生式左部所对应的非终结符放入$\rm{V_{\varepsilon}}$中\textcircled{3}重复上述过程，直到$\rm{V_{\varepsilon}}$不再扩大为止。\\
	消除文法中含有空符号串的产生式，找到文法中所有$\rm{A\rightarrow ε}$，再看A在哪些产生式中被使用了，如果这个产生式右部含有的符号恰巧是$\rm{V_{\varepsilon}}$中的，就做如下的替换：把$\rm{X_{i}}$写成$\rm{X_{i}}$或$ε$。\\
	$\divideontimes$ 若有j个$\rm{X_{i} \in V_{\varepsilon}}$,则一个产生式将分裂为$2^{\mathrm{j}}$个！\\
	\begin{example}
		\label{ex:2.19}
		$\rm{G(S):S\to aAbc|bS \quad A\to dABe|ε; B \to A|b}$
	\end{example}
	我们要求任何一个表达式的右部都不能含有空串
	
	\begin{figure}[H]
		\centering
		\input{chapter2/figures/10.tex}
		\caption{文法改写示意图}
		\label{fig:2.10}
	\end{figure}
	
	\begin{enumerate}

		\item 我们要检查这些规则的右部，哪些元素是属于$\rm{V_{\varepsilon}}$的
		\item 先把第一条中的A替换为(A|ε)，这种组合有两种再把第二条中的A和B替换为$\rm{(A|ε)}$和$\rm{(B|ε)}$，这种组合有四种最后得到$\rm{G^{\prime}(S)}$和$\rm{G(S)}$是等价的，并且$\rm{G^{\prime}(S)}$不包含产生ε的产生式
	\end{enumerate}
	\uppercase\expandafter{\romannumeral3}常用的三种文法变换方法：\\
	文法的写作上有很多方便的形式来帮助我们把一些文法表达的更简便。\\
	$\divideontimes$ 基本思想：扩展文法，引进新的描述符号：\\
	$\left(\quad \right)$圆括号； 	$\left[ \quad \right]$方括号；$\left\{\quad \right\}$花括号\\
	\textcircled{1}必选项法（圆括号法）
	令$(\alpha \mid \beta)=\alpha$或者$\beta$\\
	例如：有$\rm{A\to a\alpha|a\beta}$\\
	可变换成：$\rm{A\to a(\alpha|\beta}$)\\
	也可：$\rm{A^{A} \rightarrow A^{\prime} \quad ; \quad A^{\prime} \rightarrow \alpha \mid \beta}$\\
	【注】此法又称提公因子法，利用此法可以使文法：\\
	具有相同左部的各产生式首符号不同！\\
	这两个文法规则是等价的，只不过我们把右部的a提出来了。\\
	把圆括号的部分替换为$\rm{A^{\prime}}$，就可以得到另外两个产生式，那为什么要这么做呢？读者可以思考一下。\\
	\textcircled{2}可选项法（方括号法）\\
	令$ [\alpha]=\alpha$或者$ \varepsilon$该方法表示方括号中的内容可选也可不选\\
	例如：$\rm{S\to \alpha|\alpha \beta}$\\
	可变换成：S$\to$$\alpha$[$\beta$]\\
	也可$\rm{S \to \alpha S^{\prime} ; S^{\prime} \to \beta \mid \varepsilon}$\\
	可以把方括号中的部分用$\rm{S^{\prime}}$替换\\
	$\rm{S\to if(B)S}$\\
	$\rm{S\to if(B)S\quad else \quad S}$\\
	B为条件语句\\
	可变换成:$\rm{S\to if (B) S [else S]}$\\
	或：$\rm{S \rightarrow \text { if (B) } S S^{\prime} ; S^{\prime} \rightarrow \text { else } S \mid \varepsilon}$\\
	把后面else S的部分用方括号圈起来，表达的是可选也可以不选\\
	\textcircled{3}重复可选项法（花括号法）\\
	令$\{\alpha\}=\varepsilon$ 或 $\alpha$ 或  $\alpha \alpha$ 或 $\alpha \alpha \alpha \ldots$\\
	花括号代表无数种情况，表示由$\alpha$构成的符号串包括空串\\
	例如:$\rm{S\rightarrow A \beta|\alpha}$这个文法所生成的语言是一个什么样子的语言呢？\\
	这个文法只有A使用$\alpha$进行推导的时候才能生成终结符串，如果A推导出A$\beta$那这个推导就无法终止，$\rm{A\rightarrow A \beta \rightarrow A \beta^{2} \rightarrow A \beta^{3} 
		\rightarrow \cdots A\beta^{n}=\alpha \beta^{n},\mathrm{n}>=0}$
	可变换为：$\rm{A\rightarrow \alpha\{\beta\}}$\\
	也可$\rm{A \rightarrow \alpha A^{\prime} \quad ; \quad A^{\prime} \rightarrow \beta A^{\prime} \mid \varepsilon}$\\
	$\divideontimes$ 验证：\\
	$\because$通过递推方法，可得:\\
	$\rm{A \Rightarrow A \beta \Rightarrow A \beta \beta \Rightarrow A \beta \beta \beta \Rightarrow \ldots \Rightarrow \alpha \beta *}$\\
	$\therefore$有$\rm{A \rightarrow \alpha\{\beta\}}$ ; 或  $\rm{A \rightarrow \alpha A^{\prime} ; A^{\prime} \rightarrow \beta A^{\prime} \mid \varepsilon}$\\
	【注】此方法常用来消除文法的直接左递归！ \\
	同样我们也可以用$\rm{A^{\prime}}$来替换花括号中的内容，粉色和绿色的部分分别代表花括号的方式和文法改造的方式。\\
	白色部分的文法具有左递归，绿色部分的文法没有直接左递归，但是有递归的部分，是直接右递归。左递归和右递归在我们文法分析方法中导致的方法是完全不一样的。在后面文法分析一章会发现直接左递归文法很难分析。举个例子：比如用自上而下的分析，如果文法有直接左递归性，则采用最左推导时会导致死循环，所以在很多场景中我们要消除直接左递归。\\
	\section{形式语言的分类}
	% \begin{figure}[H]
		%     \centering
		%     \input{chapter2/figures/11.tex}
		%     \caption{形式语言分类图}
		%     \label{fig:2.11}
		% \end{figure}
	Chomsky把形式语言分为四类，分别由四类文法定义；四类文法的区别在于产生式的形式不同。
	\begin{enumerate}

		\item 0型语言由0型文法定义
		\begin{itemize}
			\item 产生式的形式为：$\alpha\rightarrow\beta$，又称无限制文法。
		\end{itemize}
		
		\item 1型语言由1型文法定义
		\begin{itemize}
			\item 产生式的形式为：$\mathrm{xAy\rightarrow x\beta y}$，又又称上下文有关文法。
		\end{itemize}
		
		\item 2型语言由2型文法定义
		\begin{itemize}
			\item 产生式的形式为：$\mathrm{A\rightarrow\beta }$，又称上下文无关文法。
		\end{itemize}
		
		\item 3型语言由3型文法定义
		\begin{itemize}
			\item 产生式的形式为：$\mathrm{A\rightarrow aB,\ A\rightarrow a,\ A\rightarrow\varepsilon}$，又称正规文法。
		\end{itemize}
	\end{enumerate}
	
	【注】四类语言为包含关系，且有$\mathrm{L_{0} \supset L_{1} \supset L_{2} \supset L_{3}}$，编译处理中主要应用后两种文法。
	
	在这门课中，用到的事2型语言和3型语言，上下文无关文法对应语法分析的部分，正规文法对应词法分析的部分。
